package com.leetcode.ask;

import java.util.*;

/**
 * @ProjectName: leetcode
 * @Package: com.leetcode.ask
 * @description: 无重复字符的最长子串
 * 第3题
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 * 示例 1:
 * <p>
 * 输入: "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * 示例 2:
 * <p>
 * 输入: "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * 示例 3:
 * <p>
 * 输入: "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 * <p>
 * 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
 * @Author: liyc
 * @CreateDate: 2020/1/6 3:47 PM
 * @Version: 1.0
 * <p>Copyright: Copyright (c) 2020</p>
 */
public class LengthOfLongestSubstring {


    /**
     * @param
     * @return
     * @description 官方题解
     * 方法二：滑动窗口
     * 算法
     * 暴力法非常简单，但它太慢了。那么我们该如何优化它呢？
     * 在暴力法中，我们会反复检查一个子字符串是否含有有重复的字符，但这是没有必要的。如果从索引 ii 到 j - 1j−1 之间的子字符串 s_{ij}s
     * ij
     * 已经被检查为没有重复字符。我们只需要检查 s[j]s[j] 对应的字符是否已经存在于子字符串 s_{ij}s
     * ij
     * 中。
     * <p>
     * 要检查一个字符是否已经在子字符串中，我们可以检查整个子字符串，这将产生一个复杂度为 O(n^2)O(n
     * 2
     * ) 的算法，但我们可以做得更好。
     * <p>
     * 通过使用 HashSet 作为滑动窗口，我们可以用 O(1)O(1) 的时间来完成对字符是否在当前的子字符串中的检查。
     * <p>
     * 滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i, j)[i,j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 [i, j)[i,j) 向右滑动 11 个元素，则它将变为 [i+1, j+1)[i+1,j+1)（左闭，右开）。
     * <p>
     * 回到我们的问题，我们使用 HashSet 将字符存储在当前窗口 [i, j)[i,j)（最初 j = ij=i）中。 然后我们向右侧滑动索引 jj，如果它不在 HashSet 中，我们会继续滑动 jj。直到 s[j] 已经存在于 HashSet 中。此时，我们找到的没有重复字符的最长子字符串将会以索引 ii 开头。如果我们对所有的 ii 这样做，就可以得到答案。
     * <p>
     * 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetcod/
     * @author liyc
     * @date 2020/1/6
     */
    public static int offical(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            // try to extend the range [i, j]
            if (!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            } else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }

    /**
     * @param
     * @return
     * @description 优化的滑动窗口
     * @author liyc
     * @date 2020/1/6
     */
    public static int officalGood(String s) {
        int n = s.length(), ans = 0;
        // current index of character
        Map<Character, Integer> map = new HashMap<>();
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }


    /**
     * @param
     * @return
     * @description 自己解法
     * 找出所有不重复的子串，倒序找出最大的
     * @author liyc
     * @date 2020/1/6
     */
    public static int lengthOfLongestSubstring(String s) {
        Map<Integer, String> map = new HashMap<>();
        String str = "";
        for (char c : s.toCharArray()) {
            if (str.indexOf(c) == -1) {
                str += c;
            } else {
                map.put(str.length(), str);
                str = str.substring(str.indexOf(c) + 1);
                str += c;
            }
        }
        map.put(str.length(), str);
        for (int i = s.length() - 1; i >= 0; i--) {
            if (null != map.get(i)) {
                return i;
            }
        }
        return str.length();
    }

    public static void main(String[] args) {
        officalGood("dvdfdx");

//        String str = "dvdfdg";
//        System.out.println(str.substring(6));
    }


}
